<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    753. Open the Lock
   </h1>
   <p>
    You have a lock in front of you with 4 circular wheels.  Each wheel has 10 slots:
    <code>
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
    </code>
    .  The wheels can rotate freely and wrap around: for example we can turn
    <code>
     '9'
    </code>
    to be
    <code>
     '0'
    </code>
    , or
    <code>
     '0'
    </code>
    to be
    <code>
     '9'
    </code>
    .  Each move consists of turning one wheel one slot.
   </p>
   <p>
    The lock initially starts at
    <code>
     '0000'
    </code>
    , a string representing the state of the 4 wheels.
   </p>
   <p>
    You are given a list of
    <code>
     deadends
    </code>
    dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
   </p>
   <p>
    Given a
    <code>
     target
    </code>
    representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
   </p>
   <p>
    <b>
     Example 1:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> deadends = ["0201","0101","0102","1212","2002"], target = "0202"
<b>Output:</b> 6
<b>Explanation:</b>
A sequence of valid moves would be "0000" -&gt; "1000" -&gt; "1100" -&gt; "1200" -&gt; "1201" -&gt; "1202" -&gt; "0202".
Note that a sequence like "0000" -&gt; "0001" -&gt; "0002" -&gt; "0102" -&gt; "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".
</pre>
   <p>
    <b>
     Example 2:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> deadends = ["8888"], target = "0009"
<b>Output:</b> 1
<b>Explanation:</b>
We can turn the last wheel in reverse to move from "0000" -&gt; "0009".
</pre>
   <p>
    <b>
     Example 3:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
<b>Output:</b> -1
<b>Explanation:</b>
We can't reach the target without getting stuck.
</pre>
   <p>
    <b>
     Example 4:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> deadends = ["0000"], target = "8888"
<b>Output:</b> -1
</pre>
   <p>
    <b>
     Note:
    </b>
    <br>
   </p>
   <ol>
    <li>
     The length of
     <code>
      deadends
     </code>
     will be in the range
     <code>
      [1, 500]
     </code>
     .
    </li>
    <li>
     <code>
      target
     </code>
     will not be in the list
     <code>
      deadends
     </code>
     .
    </li>
    <li>
     Every string in
     <code>
      deadends
     </code>
     and the string
     <code>
      target
     </code>
     will be a string of 4 digits from the 10,000 possibilities
     <code>
      '0000'
     </code>
     to
     <code>
      '9999'
     </code>
     .
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    753. 打开转盘锁
   </h1>
   <p>
    你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字：
    <code>
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
    </code>
    。每个拨轮可以自由旋转：例如把
    <code>
     '9'
    </code>
    变为&nbsp;
    <code>
     '0'
    </code>
    <font color="#333333" face="Helvetica Neue, Helvetica, Arial, sans-serif">
     <span style="background-color:#ffffff; font-size:14px">
      ，
     </span>
    </font>
    <code>
     '0'
    </code>
    变为
    <code>
     '9'
    </code>
    。每次旋转都只能旋转一个拨轮的一位数字。
   </p>
   <p>
    锁的初始数字为
    <code>
     '0000'
    </code>
    ，一个代表四个拨轮的数字的字符串。
   </p>
   <p>
    列表
    <code>
     deadends
    </code>
    包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
   </p>
   <p>
    字符串
    <code>
     target
    </code>
    代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1:
    </strong>
   </p>
   <pre>
<strong>输入：</strong>deadends = ["0201","0101","0102","1212","2002"], target = "0202"
<strong>输出：</strong>6
<strong>解释：</strong>
可能的移动序列为 "0000" -&gt; "1000" -&gt; "1100" -&gt; "1200" -&gt; "1201" -&gt; "1202" -&gt; "0202"。
注意 "0000" -&gt; "0001" -&gt; "0002" -&gt; "0102" -&gt; "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
</pre>
   <p>
    <strong>
     示例 2:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> deadends = ["8888"], target = "0009"
<strong>输出：</strong>1
<strong>解释：</strong>
把最后一位反向旋转一次即可 "0000" -&gt; "0009"。
</pre>
   <p>
    <strong>
     示例 3:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
<strong>输出：</strong>-1
<strong>解释：
</strong>无法旋转到目标数字且不被锁定。
</pre>
   <p>
    <strong>
     示例 4:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> deadends = ["0000"], target = "8888"
<strong>输出：</strong>-1
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     死亡列表
     <code>
      deadends
     </code>
     的长度范围为
     <code>
      [1, 500]
     </code>
     。
    </li>
    <li>
     目标数字
     <code>
      target
     </code>
     不会在
     <code>
      deadends
     </code>
     之中。
    </li>
    <li>
     每个
     <code>
      deadends
     </code>
     和
     <code>
      target
     </code>
     中的字符串的数字会在 10,000 个可能的情况
     <code>
      '0000'
     </code>
     到
     <code>
      '9999'
     </code>
     中产生。
    </li>
   </ol>
  </div>
 </body>
</html>